#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack
{
    STDataType* data;
    int top;
    int capacity;
}Stack;

void print(int *a, int n)
{
    for(int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    printf("\n");
}

void StackInit(Stack* s)
{
    assert(s);
    
    s->data = NULL;
    s->top = s->capacity = 0;
}

void StackPush(Stack* s, STDataType x)
{
    assert(s);

    if(s->top == s->capacity)
    {
        int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
        STDataType* tmp = (STDataType* )malloc(newcapacity * sizeof(STDataType));
        if(!tmp)
        {
            perror("malloc faild ::");
            exit(-1);
        }
        s->capacity = newcapacity;
        s->data = tmp;
    }
    s->data[s->top] = x;
    ++s->top;
}
void StackPop(Stack* s)
{
    assert(s);
    assert(s->top >= 0);
    
    --s->top;
}

STDataType StackTop(Stack* s)
{
    assert(s);
    assert(s->top >= 0);

    return s->data[s->top - 1];
}

bool StackEmpty(Stack* s)
{
    assert(s);

    return s->top == 0;
}
void Swap(int*a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
int GetMiniInsid(int* a, int begin, int end)
{
    int mini = begin + ((end - begin) >> 1);
    if(a[begin] > a[mini])
    {
        if(a[mini] > a[end])
            return mini;
        else  if (a[begin] > a[end])
            return end;
        else 
            return begin;
    }
    else
    {
        if(a[end] > a[mini])
            return mini;
        else if (a[begin] > a[end])
            return begin;
        else 
            return end;
    }
}
int partion3(int* a, int begin, int end)
{
    int mini = GetMiniInsid(a, begin, end);
    Swap(&a[begin], &a[mini]);

    int keyi = begin;
    int prev = keyi;
    int cur = prev + 1;
    while(cur <= end)
    {
        if(a[cur] < a[keyi] && prev != cur)
            Swap(&a[++prev], &a[cur]); 
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}
void quicksort(int* a, int left, int right)
{
    if (left > right)
        return ;
    //int keyi = partion1(a, left, right);
    //int keyi = partion2(a, left, right);
    Stack s;
    StackInit(&s);
    StackPush(&s, right);
    StackPush(&s, left);
    while(!StackEmpty(&s))
    {
        int begin = StackTop(&s);
        StackPop(&s);
        int end = StackTop(&s);
        StackPop(&s);

        int keyi = partion3(a, begin, end);
        if(begin < keyi - 1)
        {
            StackPush(&s, keyi - 1);
            StackPush(&s, begin);
        }
        if(end > keyi + 1)
        {
            StackPush(&s, end);
            StackPush(&s, keyi + 1);
        }
    }

}
int main()
{
    int a[10] = { 12, 10, 6, 8, 18, 5, 40, 3, 1, 9 };
    quicksort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
    print(a, sizeof(a) / sizeof(a[0]));
    return 0;

}
